#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode*left;
    struct TreeNode*right;
    TreeNode(int x):
        val(x),
        left(NULL),
        right(nullptr){};
};

class Solution 
{
    public:
    // 在公共代码区实现你的函数
    // 只需返回一组解，因此是vector<int>
    vector<int> pathSum(TreeNode* root, int sum) 
    {
        vector<int>path;
        vector<int>res;
        // 标准思路，使用递归对结果数组进行变化
        dfs(root, sum, path, res);
        return res;
    }
    
    private:
    // 注意这里是传值调用sum，因为每次递归都要更新sum
    void dfs(TreeNode* node, int sum, vector<int>& path, vector<int>& res)
    {
        // 第一步: 如果节点为空，直接返回，当然也是递归终止条件
        if (!node)
        {
            return;
        }

        // 第二步: 将当前节点加入路径，并更新剩余和
        path.push_back(node->val);
        sum -= node->val;

        // 第三步: 到达叶子节点，检查路径和是否等于目标值，
        // 检查方式为左右节点都为空
        // 同时还要保证总和恰好全都减没
        if (!node->left && !node->right && sum == 0)
        {
            res = path; // 找到一组解，保存路径
            return;
        }

        // 第四步: 分别对左右节点继续走下去，并且传值调用sum
        dfs(node->left, sum, path, res);
        dfs(node->right, sum, path, res);

        // 回溯将上一次加入的东西取消掉
        path.pop_back();
    }
};

TreeNode*build_tree(vector<int>&vals, int index)
{
    // 递归终止条件
    if (index >= vals.size() || vals[index] == -1)
    {
        // 如果值为负一或者下标越界则返回空节点
        // 将空节点作为叶子节点的子节点
        return nullptr;
    }

    // 从空节点往上层构建
    // 返回当前节点作为父节点的子节点
    TreeNode*root = new TreeNode(vals[index]);
    root->left = build_tree(vals, 2*index + 1);     // 2*index + 1表示左子节点下标
    root->right = build_tree(vals, 2*index + 2);    // 2*index + 2表示右子节点下标 
    return root;
}

int main()
{
    vector<int>vals = {3,9,29,-1,-1,15,7};
    TreeNode*root = build_tree(vals,0)  ;

    Solution*s = new Solution;
    vector<int> res = s->pathSum(root,1);
    for (int i:res)
    {
        cout<<i<<"\n";
    }
        
    return 0;
}
